#include<string.h>
#include<cstring>
#include<iostream>

#include<algorithm>

using namespace std;
const int N=1100;
char h[N][15];
int f[15][15];

int dp(char a[], char b[]){
    int n1=strlen(a+1);
    int n2=strlen(b+1);
 
    
    for(int i=0;i<=n1;i++)f[i][0]=i;
    
    for(int i=0;i<=n2;i++)f[0][i]=i;
    
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=n2;j++){
            f[i][j]=min(f[i][j-1]+1,f[i-1][j]+1);
            if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    return f[n1][n2];
    
}


int main(){
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<n;i++){
       scanf("%s",h[i]+1);
    }
    
    while(m--){
        char s[15];
        int d;
        int res=0;
        scanf("%s%d",s+1,&d);
        for(int i=0;i<n;i++){
     
            int k=dp(h[i],s);
            if(d>=k)res++;
        }
        cout<<res<<endl;
        
        
        
    }
    
    return 0;
}
